(1) Field of the Invention
The invention relates to compression encoding. More specifically, the invention relates to achieving higher speed encodings with reduced hardware complexity.
(2) Related Art
In data transmission systems, data arrives as symbols of variable size. A symbol is a number of bits of valid data up to some maximum symbol size which is usually dictated by the hardware of the system. Typically, a maximum symbol size is the maximum number of bits that may be sent in one transaction. Typical values are 16 bits or 32 bits. If the symbols are not encoded, each symbol regardless of size is transferred as a packet to the recipient. Because transfers tend to be relatively slow, it is desirable to transfer as much data per transfer as possible. To this end, compression encoding techniques have been developed to pack symbols and portions of symbols together so as to yield a packet having a maximum symbol size of valid data at each transfer.
FIG. 1 illustrates this technique using prior art on a smaller scale in which the packet size has been assumed to be four bits. A pointer 101 is maintained to point to the first available location in a packing register 100 to which an incoming symbol may be written. FIG. 1 shows the packing register 100 during four cycles. During a cycle 105, no data has been written, and the register 100 is empty. In cycle 106, a 3-bit symbol, AAA, has been written to register 100, and pointer 101 now points to the 4th location in register 100. In a cycle 107, another 3-bit symbol, BBB, is written to the register 100. This results in the written data and the pointer 101 crossing a boundary 102. The data to the left of the boundary 102, "AAAB," represents a maximum symbol size, and a read of that data is initiated. In the next cycle 108, the data written beyond boundary 102 must be shifted to the other side of the boundary and a write of the single bit value, C, initiated. To accomplish this shifting and allow for the write during a single cycle 108, this, the simplified example, would require four 7-to-1 multiplexors and seven 4-to-1 multiplexors. In a more realistic example in which the maximum symbol size is 16 and a 31 bit register is employed, 16 15-to-1 multiplexors and 31 16-to-1 multiplexors would be required in order to do the shift and bit packing in one cycle.
In view of the foregoing, it is desirable to simplify the hardware without a loss of speed. Thus, for example, it is desirable to be able to read and write a symbol of up to a maximum size in every cycle.